package algorithm;

import java.util.Arrays;

/**
 * @description: 类描述
 * @author: Fesine
 * @createTime:2017/8/2 11:12
 * @update:修改内容
 * @author: Fesine
 * @updateTime:2017/8/2 11:12
 */
public class BubbleSort {

    /**
     * 冒泡排序
     * 算法描述：对于给定的n个记录，
     * 从第一个记录开始依次对相邻的两个记录进行比较，
     * 当前面的记录大于后面的记录时，交换位置，
     * 进行一轮比较和交换后，n个记录中的最大记录将位于第n位；
     * 然后对前（n-1）个记录进行第二轮比较；
     * 重复该过程直到进行比较的记录只剩下一个为止。
     * 平均O(n^2),最好O(n),最坏O(n^2);空间复杂度O(1);稳定;简单
     * 49,38,65,97,76,13,27,50
     *
     * @param sorted
     */
    public static void bubbleSort(int[] sorted) {
        int n = sorted.length;
        int tmp;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (sorted[j] > sorted[j + 1]) {
                    tmp = sorted[j];
                    sorted[j] = sorted[j + 1];
                    sorted[j + 1] = tmp;
                }
            }
        }
    }

    public static void bubbleSort2(int[] sorted) {
        int tmp;
        for (int i = sorted.length - 1; i > 1; i--) {
            for (int j = 0; j < i; j++) {
                if (sorted[j] > sorted[j + 1]) {
                    tmp = sorted[j];
                    sorted[j] = sorted[j + 1];
                    sorted[j + 1] = tmp;
                }
            }
        }
    }


    public static void main(String[] args) {
        int[] a = {49, 38, 65, 97, 76, 13, 27, 50};
        bubbleSort2(a);
        System.out.println(Arrays.toString(a));
    }
}
